package com.linran.structure_algorithm.算法.常用算法.a2_分治算法;

/**
 * 将大的问题拆解成小的问题，得出结构后合并
 */
public class HanoiTower {

    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔游戏的演示和思路分析:
     * 1) 如果是有一个盘，A->C
     * <p>
     * 如果我们有n>=2情况，我们总是可以看做是两个盘1.最下边的盘2. 上面的盘
     * 1) 先把最上面的盘A->B
     * 2) 把最下边的盘A->C
     * 3) 把B塔的所有盘从B->C
     *
     * @param num 第几个盘
     * @param a
     * @param b
     * @param c
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) {
            // 一个盘 A -> C
            System.out.println("将" + num + "盘 " + a + "->" + c);
        } else { //大于等于2
            //最上面的盘A->B
            hanoiTower(num - 1, a, c, b);
            //最下边的盘A->C
            System.out.println("将" + num + "盘 " + a + "->" + c);
            //B塔剩下的移动到C
            hanoiTower(num - 1, b, a, c);
        }
    }
}
